home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / answrbok / 5_2.lha / 5_2 / 5_2b3.c < prev    next >
Text File  |  1993-08-08  |  1KB  |  80 lines
  1. * Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
  2. * The C++ Answer Book */
  3. * Tony Hansen */
  4. * All rights reserved. */
  5. / delete a word from the tree
  6. include <tree.h>
  7. include <string.h>
  8.  
  9. nt tree:: delnode(char *s)
  10.  
  11.    tnode **parent = &head;
  12.    tnode *cur = head;
  13.  
  14.    for (;;)
  15. {
  16. if (!cur)
  17.     return 0;
  18.  
  19. int cmp = strcmp(s, cur->tword);
  20.  
  21. // check the left subtree
  22. if (cmp < 0)
  23.     {
  24.     parent = &cur->left;
  25.     cur = cur->left;
  26.     }
  27.  
  28. // check the right subtree
  29. else if (cmp > 0)
  30.     {
  31.     parent = &cur->right;
  32.     cur = cur->right;
  33.     }
  34.  
  35. // equal, found it
  36. else /* if (cmp == 0) */
  37.     {
  38.     // if more than one reference,
  39.     // just decrement the reference count
  40.     if (cur->count > 1)
  41.     cur->count--;
  42.  
  43.     // if there are no children,
  44.     // delete this node and
  45.     // the reference to it
  46.     else if (!cur->left && !cur->right)
  47.     {
  48.     delete cur;
  49.     *parent = 0;
  50.     }
  51.  
  52.     // if there are children, try doing
  53.     // a splice into the right node
  54.     else if (!cur->right->left)
  55.     {
  56.     *parent = cur->right;
  57.     cur->right->left = cur->left;
  58.     delete cur;
  59.     }
  60.  
  61.     // find a node on the left where
  62.     // we can splice in the right node
  63.     else
  64.     {
  65.     tnode *svright = cur->right;
  66.     *parent = cur->left;
  67.     delete cur;
  68.  
  69.     for (cur = *parent;
  70.          cur->right;
  71.          cur = cur->right)
  72.         ;
  73.     cur->right = svright;
  74.     }
  75.  
  76.     return 1;
  77.     }
  78. }
  79.  
  80.